package 动态规划;


import java.util.ArrayList;
import java.util.List;

public class Algo931 {

    private static int[][] dp;

    public static int minFallingPathSum(int[][] matrix) {
        if(matrix.length == 1) {
            return matrix[0][0];
        }

        int result = Integer.MAX_VALUE;
        int n = matrix.length;

        dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            result = Math.min(result, dp(matrix, n-1, i));
        }
        return result;
    }

    private static int dp(int[][] matrix, int i, int j) {
        if(i<0 || j<0|| i>=matrix.length || j>=matrix.length) {
            return Integer.MAX_VALUE;
        }

        if(dp[i][j] !=0) {
            return dp[i][j];
        }

        if(i == 0){
            return matrix[i][j];
        }

        int result =  matrix[i][j] + min(dp(matrix, i-1, j-1), dp(matrix, i-1, j), dp(matrix, i-1,j+1));
        dp[i][j] = result;
        return result;
    }

    private static int min(int dp0, int dp1, int dp2) {
        return Math.min(Math.min(dp0,dp1),dp2);
    }

    public static void main(String[] args) {
        int[][] arr = {{-19,57},{-40,-5}};
        System.out.println(minFallingPathSum(arr));
    }
}
